home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 007 / bmgrep.arc / MAKESKIP.C < prev    next >
Text File  |  1986-12-10  |  1KB  |  47 lines
  1. #include <stdio.h>
  2. #include "bm.h"
  3. extern char *malloc();
  4.  
  5. MakeSkip(Pattern,Skip1,Skip2,PatLen)
  6. char Pattern[];
  7. unsigned short int Skip1[], Skip2[];
  8. int PatLen;
  9. /* generate the skip tables for Boyer-Moore string search algorithm.
  10. * Skip1 is the skip depending on the character which failed to match
  11. * the pattern, and Skip2 is the skip depending on how far we got into
  12. * the pattern. Pattern is the search pattern and PatLen is strlen(Pattern) */
  13. {
  14.     int *BackTrack; /* backtracking table for t when building skip2 */
  15.     int c; /* general purpose constant */
  16.     int j,k,t,tp; /* indices into Skip's and BackTrack */
  17.  
  18.     if (!(BackTrack = (int *) malloc(PatLen * (sizeof (int))))){
  19.         fprintf(stderr,"bm: can't allocate space\n");
  20.         exit(2);
  21.     } /* if */
  22.     for (c=0; c<=MAXCHAR; ++c)
  23.         Skip1[c] = PatLen;
  24.     for (k=0;k<PatLen;k++) {
  25.         Skip1[Pattern[k]] = PatLen - k - 1;
  26.         Skip2[k] = 2 * PatLen - k - 1;
  27.     } /* for */
  28.     for (j=PatLen - 1,t=PatLen;j >= 0; --j,--t) {
  29.         BackTrack[j] = t;
  30.         while (t<PatLen && Pattern[j] != Pattern[t]) {
  31.             Skip2[t] = min(Skip2[t], PatLen - j - 1);
  32.             t = BackTrack[t];
  33.         } /* while */
  34.     } /* for */
  35.     for (k=0;k<=t;++k)
  36.         Skip2[k] = min(Skip2[k],PatLen+t-k);
  37.     tp=BackTrack[t];
  38.     while(tp<PatLen) {
  39.         while(t<PatLen) {
  40.             Skip2[t] = min(Skip2[t],tp-t+PatLen);
  41.             ++t;
  42.         } /* while */
  43.         tp = BackTrack[tp];
  44.     } /* while */
  45.     free(BackTrack);
  46. } /* MakeSkip */
  47.